前面四题都比较简单,搞快一点
A:比较显然的的是,n是1的时候答案是0,n是2的时候答案是m,其余的情况观察样例最多是2m
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
if(n == 1) printf("0\n");
else if (n == 2) printf("%d\n",m);
else printf("%d\n",2 * m);
}
return 0;
}
B:开两个堆,一共迭代最多K次,每次从a里面找出最小的,从b里面找出最大的,把两者交换一下,如果发现交换没有价值的时候说明可以提前退出了。
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,k,x;scanf("%d%d",&n,&k);
priority_queue<int,vector<int>,greater<int> >pa;
priority_queue<int,vector<int>,less<int> > pb;
for(int i = 1;i <= n;++i)
scanf("%d",&x),pa.push(x);
for(int i = 1;i <= n;++i)
scanf("%d",&x),pb.push(x);
for(int i = 1;i <= k;++i)
{
int ta = pa.top();pa.pop();
int tb = pb.top();pb.pop();
if(ta < tb)
{
pa.push(tb);
pb.push(ta);
}
else
{
pa.push(ta);
pb.push(tb);
break;
}
}
int res = 0;
while(!pa.empty())
{
res += pa.top();
pa.pop();
}
printf("%d\n",res);
}
return 0;
}
C:可以猜出一个结论,那就是想要所有距离最短,肯定是所有的都最短,那么就是所有的点都往中心走就可以了,题目又刚好说n一定是奇数,于是可以果断猜出结论就是全部往中心走。接着可以发现数字的规律是一圈一圈增大的,中心是0,往外环绕一圈的是1,再往外就是2,因此可以推出规律:对于当前在考虑的数字,它一共出现了次,总数是个,因此答案就是
res =
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
ll n;scanf("%lld",&n);
ll res = 0;
for(ll i = 1;i <= n;i += 2)
res += (i / 2) * 8 * (i / 2);
printf("%lld\n",res);
}
return 0;
}
D:维护一个堆,里面的元素带两个值,第一个是总长度len,第二个是左端点l。每次从堆里面取出len最大的元素,以及l最小的元素,注意:由于第一关键字按最大的排序,因此l在插入的时候是插入的负l,做的时候要转换。
typedef long long ll;
typedef pair<int,int> pii;//len&lp
const int N = 2e5+7;
int res[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
if(n == 1)
{
printf("1\n");
continue;
}
priority_queue<pii> pq;
pq.push({n,-1});
int i = 1;
while(!pq.empty())
{
pii t = pq.top();pq.pop();
int len = t.first,l = -t.second;
int r = l + len - 1;
int pos = (r - l + 1) % 2 == 1 ? (l + r) / 2 : (l + r - 1) / 2;
res[pos] = i++;
//left
if(pos - l > 0) pq.push({pos - l,-l});
//right
if(r - pos > 0) pq.push({r - pos,-pos - 1});
}
for(int i = 1;i <= n;++i) printf("%d ",res[i]);
puts("");
}
return 0;
}
E:
题意:给定一个长度为的只有01的字符串,和一个数值。你可以执行一个操作:选择字符串中的一个数字让他反转,现在要求字符串中每一对1的之间恰好有个0,问最少要执行多少次操作。
注意:字符串并不是一个环形的,不要求第一个必须也跟最后一个环上满足,同时你也可以让所有的变成0,这也是满足题意得。
数据范围:组数据
且
分析:如果我们把原字符串S分成K组,按分,可以发现,对于一个合法方案来说,一定是只有其中某一组可以存在,而其他的所有组都不能存在,必须全部划到。因此第一步首先分组并求出每一组自身的数值和,数值和等价于让这一组数全部推成的代价。进而,我们可以枚举每一组数作为能存在的序列的时候,所需要的总代价,这分为两个部分:一是把其他序列推成的代价,二是把当前这个序列推成带有一且合法的序列,前面一个部分比较好算,计算所有序列的和再把当前这一组的和挖掉就可以了,对于第二部分,首先一个合法的序列是形如一段连续的,一段连续的,一段连续的0这样的序列考虑dp,记是当前字符串p中,让末尾的1出现在p位置的最小代价,不难发现dp转移只有两种来源,一是位置就是第一个,这时,即让前面推成0的代价;二是前面有,当前的是末尾,此时,这里要注意的是,如果不是,则需要对之额外增加的代价。
那么,记是把组字符串作为存在序列的代价,可以推出:
其中 即末尾p之前的代价和p之后推到0的代价总和,表示在中取最小值。
最后,实际的答案
(我的代码实现比较复杂,如果能自己写出来更好)
typedef long long ll;
const int N = 1e6+7;
char s[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,k;scanf("%d%d",&n,&k);
scanf("%s",s);
int tot = 0;
for(int i = 0;i < n;++i) tot += s[i] - '0';
vector<string> groups(k);
for(int i = 0;i < n;++i)
groups[i % k].push_back(s[i]);
int res = 1e9+7;
for(int j = 0;j < k;++j)
{
string& s = groups[j];
int sz = s.size();
int ptot = 0,fres,pref = 0;
for(int i = 0;i < sz;++i) ptot += s[i] - '0';
fres = ptot;
vector<int> fp(sz,0);
for(int i = 0;i < sz;++i)
{
fp[i] = 1 - int(s[i] == '1');
if(i > 0) fp[i] = min(fp[i - 1],pref) + (s[i] != '1');
pref += s[i] == '1';
fres = min(fres,fp[i] + ptot - pref);
}
res = min(res,fres + tot - ptot);
}
printf("%d\n",res);
}
return 0;
}
F:
题意: 有一个的棋盘,棋盘上有一些数字,起始时你在上,你想要移动到这个位置上,每次移动,你只能从当前位置向右走和向下走,且必须满足目标位置的数字是刚好等于当前位置上的数的。为了保证你可以从起始位置走到终点,你可以在走之前执行若干次以下这种操作:把某个位置上的数,问你能从起始位置走到终点位置,最少需要的操作是多少次。
注意:你可以修改起始位置的数值,数值也可以修改到负数。
数据范围:T组数据
分析:最少次数,联想到bfs,但是这个题单纯的从起点搜到终点肯定没法对值进行操作,进一步的可以贪心想到可能会有一个作为基准的值:对于某一个修改方案来说,一定至少存在某一个点的值是没有修改过的,因为假如所有的点都被修改了,那么这个所有数都修改的方案,一定对应着某一个至少有一个数没有修改过的方案(把所有数都+1相当于没加),并且后者的操作次数更少,因此对于某个合法的修改方案来说一定至少有一个没有被修改的值。这启发我们可以枚举每个位置的值作为基准,作为那个前后修改过后不变的值,进而推出所有其他的值。
假设这个棋盘是有位置的(这么做的原因是相对坐标比较好算,从题目给的那个起始开始算要算一些加一减一的问题),设表示,点修改到合法方案时的值;点是当前枚举的那个不动点,则对于不动点来说,有:,因为每次移动的时候都必须是下一个位置值恰好增大,所以坐标之和就是差,故可以根据这个式子直接推出,同时对于其他点,最终要修改到的值也就可以推出来了。
接下来枚举不动点,从每个不动点开始搜bfs就可以了,不过这里要从不动点分别往左上和右下搜索。对于下一个拓展的位置来说,必须要满足,才可以拓展,并且新的路径和就是修改次数,直接加进去就可以,最终答案就是。
这里在具体实现上来说,需要使用优先队列bfs,元素是一对坐标值,这里重载了的比较器,使之就是当前最小的值。
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
const int N = 105;
ll INF = 0x3f3f3f3f3f3f3f3f,res;
ll dist[N][N];
struct cmp
{
bool operator()(const pii& a,const pii& b)
{
return dist[a.x][a.y] > dist[b.x][b.y];
}
};
ll a[N][N];
int n,m;
void bfs(int sx,int sy)
{
memset(dist,0x3f,sizeof dist);
priority_queue<pii,vector<pii>,cmp> pq;
pq.push({sx,sy});
dist[sx][sy] = 0;
ll b = a[sx][sy] - sx - sy;
while(!pq.empty())
{
pii t = pq.top();pq.pop();
int x = t.x,y = t.y;
if(x - 1 >= 0 && a[x - 1][y] >= b + x - 1 + y
&& dist[x - 1][y] > dist[x][y] + a[x - 1][y] - (b + x - 1 + y))
{
dist[x - 1][y] = dist[x][y] + a[x - 1][y] - (b + x - 1 + y);
pq.push({x - 1,y});
}
if(y - 1 >= 0 && a[x][y - 1] >= b + x + y - 1
&& dist[x][y - 1] > dist[x][y] + a[x][y - 1] - (b + x + y - 1))
{
dist[x][y - 1] = dist[x][y] + a[x][y - 1] - (b + x + y - 1);
pq.push({x,y - 1});
}
}
pq.push({sx,sy});
while(!pq.empty())
{
pii t = pq.top();pq.pop();
int x = t.x,y = t.y;
if(x + 1 <= n && a[x + 1][y] >= b + x + 1 + y
&& dist[x + 1][y] > dist[x][y] + a[x + 1][y] - (b + x + 1 + y))
{
dist[x + 1][y] = dist[x][y] + a[x + 1][y] - (b + x + 1 + y);
pq.push({x + 1,y});
}
if(y + 1 <= m && a[x][y + 1] >= b + x + y + 1
&& dist[x][y + 1] > dist[x][y] + a[x][y + 1] - (b + x + y + 1))
{
dist[x][y + 1] = dist[x][y] + a[x][y + 1] - (b + x + y + 1);
pq.push({x,y + 1});
}
}
res = min(res,dist[1][1] + dist[n][m]);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
scanf("%lld",&a[i][j]);
res = INF;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
bfs(i,j);
printf("%lld\n",res);
}
return 0;
}
DP solution:
这个题目规定的行进路线是从起始点到最右下角,同时只能向右和向下走,这可以联系到一个很简单的DP路径问题:每个点上的权值都是固定的,从某个点走到另一个点,如果合法则增加一个值,如果不合法那么下一步的位置上就是障碍。
因此在上面分析过后,事实上DP解也是比较好想到的,首先也是枚举所有点作为基准的情况,其次每次从开始往右方向和下方向递推,如果合法就记录当前位置权值+1和下一个点的差值,否则就直接设置成,最终答案是所有到最终点的最小权值和的最小值。
DP:
状态:表示走到最小的花费。
入口:初始,若起始点无法到达()则直接返回
出口:
转移:要注意为横和竖边角单独处理,其余的时候有:
当时,当前是可以到达的,遂更新
typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second
const int N = 105;
ll INF = 0x3f3f3f3f3f3f3f3f, res;
ll dist[N][N];
ll a[N][N];
int n, m;
ll dp(int sx, int sy)
{
memset(dist, 0x3f, sizeof dist);
ll b = a[sx][sy] - sx - sy;
if(a[1][1] < b + 2) return INF;
dist[1][1] = a[1][1] - (b + 2);
for(int i = 2;i <= m;++i)
if(a[1][i] >= b + 1 + i)
dist[1][i] = a[1][i] - (b + 1 + i) + dist[1][i - 1];
for(int i = 2;i <= n;++i)
if(a[i][1] >= b + i + 1)
dist[i][1] = a[i][1] - (b + i + 1) + dist[i - 1][1];
for (int i = 2; i <= n; ++i)
for (int j = 2; j <= m; ++j)
if (a[i][j] >= b + i + j)
dist[i][j] = a[i][j] - (b + i + j) + min(dist[i - 1][j],dist[i][j - 1]);
return dist[n][m];
}
int main()
{
int T; scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%lld", &a[i][j]);
res = INF;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
res = min(dp(i, j), res);
printf("%lld\n", res);
}
return 0;
}
此外,上面的代码是使用的有哪些状态组成,如果写成出边转移的方式的话会更简单一些,不需要像上面那样写特殊处理
ll dp(int sx, int sy)
{
memset(dist, 0x3f, sizeof dist);
ll b = a[sx][sy] - sx - sy;
if(a[1][1] < b + 2) return INF;
dist[1][1] = a[1][1] - (b + 2);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
{
if(i + 1 <= n && a[i + 1][j] >= b + i + 1 + j)
dist[i + 1][j] = min(dist[i + 1][j],a[i + 1][j] - (b + i + 1 + j) + dist[i][j]);
if(j + 1 <= m && a[i][j + 1] >= b + i + j + 1)
dist[i][j + 1] = min(dist[i][j + 1],a[i][j + 1] - (b + i + j + 1) + dist[i][j]);
}
return dist[n][m];
}